1. Field of the Invention
The present invention relates generally to prime number searching, and more specifically to a system and method for providing cryptographic parameters in response to requests therefor with a minimum amount of latency.
2. Description of the Prior Art
Many different types of cryptographic security systems require a means for determining large prime numbers. As an example, public key cryptographic schemes require large prime numbers to produce cryptographic keys which are used to encipher and decipher data for the purposes of guaranteeing the confidentiality, reliability, and authenticity of information to be stored or transferred from one place to another. As an example, a bank requires some means for keeping financial transactions confidential, and for guaranteeing the authenticity of a financial transaction in order to prevent the wrongful transfer of money.
In a typical cryptographic scheme, an encryption process is performed to transform a plaintext message M into ciphertext C, and a decryption process is performed to transform the ciphertext C back into the plaintext message M. In a public key cryptographic scheme, encryption and decryption processes are performed using a pair of cryptographic keys that are produced based on large prime numbers that meet certain criteria. In the most common application, a public key E defined as the pair {e, n} is used to encrypt a message into ciphertext, and a private key D defined as the pair {d, n}is typically used to decrypt the ciphertext. It is important to note that the public key E, which may be publicly known, cannot be used to decrypt the ciphertext. Only the private key D, which is kept secret, can be used for decryption of a message encrypted by the public key E. As an example, consider that a sender needs to send an encrypted message M to a recipient. The recipient publishes his or her public key, making it known at least to the sender, and keeps his or her private key secret. The sender then uses the public key to encrypt a message, and send the encrypted message to the recipient who then uses the private key to decrypt the message. Any third party interpreting the encrypted message is unable to decrypt the message without knowing the private key. As further explained below, although the public key is related to the private key, it is computationally difficult to determine the private key from the public key.
One example of a public key cryptography system is the classic “RSA” scheme which capitalizes on the relative ease of generating a composite number as the product of two large prime numbers, as compared with the difficulty of factoring that composite number into its constituent prime numbers. Another example of a public key cryptography system is the Multiprime extension of the RSA system which is described in U.S. patent application Ser. No. 09/328,726, filed on Oct. 26, 1998, by Collins et al. This system also relies for its security on the difficulty of factoring a composite into its constituent prime factors.
The classic two-prime RSA scheme uses a public key E including a composite number n and a number e, where n is defined by relationship (1), below.n=p·q  (1)
where the factors p and q are different prime numbers, and e is a number relatively prime to (p−1) and (q−1). Importantly, the sender has access to the public key E (including n and e), but not to the prime factors p and q, which are kept secret by the owner.
The sender enciphers a message M (where M<n) to create ciphertext C by computing the exponential relationship (3), below.C≡Me(mod n)  (3)
wherein the number e provides a public exponent (or encryption exponent), and the composite number n provides a modulus. The recipient of the ciphertext C may decrypt the message M using the private key D, which includes a number d and the modulus n, in accordance with relationship (4), below.M≡Cd(mod n)  (4)
The number d, which provides a private exponent (or decryption exponent), is a multiplicative inverse ofe(mod(1 cm((p−1), (q−1))))  (5)
so thate·d≡1(mod(1 cm((p−1), (q−1))))  (6)
where 1 cm((p−1), (q−1)) is the least common multiple of the numbers (p−1) and (q−1).
Most commercial implementations of the RSA cryptography scheme employ a different although equivalent relationship (7), below, for determining a private exponent d.d≡e−1 mod ((p−1)(q−1))  (7)
The security of this cryptographic system relies on the fact that the prime factors p and q of the composite number n are required to determine d and thus to decrypt the ciphertext C, and it is computationally difficult to factor the composite number n into its prime factors p and q.
Cryptanalysis refers to techniques for deciphering encrypted data without prior knowledge of the keys being used. From the time a security scheme becomes publicly known and used, it is subjected to unrelenting attempts to break it. Security levels for encryption schemes are periodically being raised in order to combat increasingly more intelligent or powerful cryptanalytic attacks.
Cryptanalysts are often more interested in discovering the cryptographic keys E and D which are used to decrypt data than in merely discovering the contents of a single message. The most basic method of finding a decryption key is to try all possibilities by an exhaustive key search until the correct key is found. A more sophisticated method is to attempt to factor the modulus n. One method for increasing the security level provided by a public key cryptography system is to increase the length Ln (i.e., size in bits) of the modulus n so that the prime factors p and q cannot be discovered by an exhaustive search or by practical factoring methods. As an example, very large modulus numbers having a long length Ln (e.g., on the order of 512 bits, 768 bits, 1024 bits, and 2048 bits) are now being used in cryptographic keys. In the classic 2-prime RSA encryption algorithm, each of the prime factors p and q has a length Lprime which is equal to half the bit length Ln, of the modulus n. For example, if the modulus has a length Ln, of 1024 bits, then each of the prime factors p and q would have a length Lprime of 512 bits. Using cryptographic keys of this size requires a significant amount of computer resources to perform the encryption and decryption operations, but also require much greater resources of a potential attacker to discover the decryption key.
One tradeoff resulting from use of such large cryptographic key values is that the amount of computer processing power required to create a new key pair increases as the lengths of the prime factors increases. The generation of cryptographic keys based on large prime numbers (such as for use in the classic two-prime RSA public key cryptosystem, and in the MultiPrime extension of the RSA system) requires total operations on the order of the key length L (in bits) taken to the fourth power. As the need for stronger security forces an increase in the lengths of modular numbers used in the RSA public key cryptosystems from 512 to 1024, 2048, and 4096 bits, the time and cost of computer resources for generation of a new cryptographic key grows correspondingly in the ratios 1 to 16 to 256 to 4096.
In particular, an increasingly important performance issue is the time and processing power required for prime number generation. Prime number generation refers to processing steps involved in searching for and verifying large prime numbers that meet certain criteria for use in cryptographic keys. Testing the primality of large candidate numbers is very processing intensive. Efficient prime number generation is becoming more important due to several technical developments besides the demand for increased cryptographic key lengths. First, encryption and decryption processes are now being employed for use with inexpensive, processing power limited devices (e.g., cell phones and personal digital assistants (PDA's)). Therefore, it would be desirable to reduce the processing time required for the task of large prime number generation so that the processing resources of even a cell phone or PDA could accomplish the task. Second, there is an ever increasing demand for more cryptographic keys. Smart cards are now being provided with unique public keys.
The most common technique for determining prime numbers is a search method which generally includes the steps of: generating a random odd number n0 in a predefined interval (e.g., the interval between 2L-1 and 2L); determining if the number n0 is a prime number; and if n0 is not a prime number, selecting another candidate n1 in the predefined interval and determining if it is a prime number; and repeating these steps until a prime number is found. A large amount of time and processing power is required to find prime numbers because the relative frequency of occurrence of prime numbers decreases with size. The relative frequency of occurrence of a randomly generated number being prime depends on the size of the number. As an example, for a random number n0 generated in the interval between 2L-1 and 2L, the probability that n0 is prime is roughly equal to 1/L or more approximately 1/(L.ln2). Therefore, the probability that a generated number having a length L is a prime number is inversely proportional to the length of the number. This presents an important problem in public key type cryptography systems where the level of security is dependent at least in part on the length L of the cryptographic keys because increasing the length L to enhance the level of security results in a decrease in the performance of the prime number generation system.
Primality testing, that is the sub-process of determining if a randomly generated number n0 is a prime number, is the most processing intensive aspect of prime number generation. Primality testing may be accomplished using any one of a wide variety of different techniques, or using a combination of different techniques. Probabilistic primality tests provide methods by which arbitrary positive integers are tested to provide partial information regarding their primality. As further explained below, conventional probabilistic primality testing typically utilizes a plurality of sequentially executed primality tests, each being performed including an exponentiation with respect to an associated base integer αi where 1≦i≦t. Any single execution of a probabilistic primality test on a number results in a declaration of the number as being either a possible prime or a definite composite. A result of execution of a primality test which declares the number to be composite establishes this with certainty, while a result which declares the number to be a probable prime does not establish primality with certainty. However, execution of a plurality of t successive independent primality tests, each indicating that the integer may be prime, provides for a cumulative probability of error that decreases as the number t increases. If the test is run t times independently on a composite number n, the probability that n is declared possible prime all t times (i.e., the probability of error) is at most (½)t, and may be much smaller.
Commonly used probabilistic primality tests include the Fermat primality test and the Miller-Rabin primality test. Fermat's theorem asserts that if n is a prime, and αi is any integer, 1≦αi≦n−1, then relationship (8), below, is true.αin-1≡1(mod n) where 1≦i≦t  (8)
If congruency is not found in accordance with relationship (8), that is if the statement defined by relationship (8) is not true, then α1 is said to be a “Fermat witness” to compositeness for n. If n is a composite number, and congruency is found in accordance with relationship (8), then n is said to be a pseudoprime to the base αi, and the integer αi is called a non-witness or “Fermat liar” to the compositeness of n.
Computer readable instructions for implementing each iteration of relationship (8) may be executed by a processor to determine the veracity of relationship (8) which yields a result declaring either probable primality or compositeness. As mentioned above, for probabilistic primality tests such as the Fermat test, if the results of relationship (8) declare “prime”, then there is no absolute proof that the number n is indeed prime. Therefore, exponentiation tests in accordance with relationship (8) are typically repeated t times for α1, α2, . . . αt to determine if each of the t tests declares “prime” in order to achieve an acceptable level of certainty that the candidate is a prime. It is still true that if the prime number candidate passes all of the congruency tests for α1, α2, . . . αt, then there is no guarantee that the candidate is a prime. However, if the prime number candidate P is a composite number, then it will fail at least one of the congruency tests for α1, α2, . . . αt with a high probability.
Because relationship (8) defines an exponentiation, a significant amount of time and processing resources are required to execute instructions for implementing relationship (8). In order to accelerate the prime number generation process, conventional prime number generation systems typically provide a processor and a single exponentiation unit communicatively coupled with the processor in order to reduce the burden on the processor and speed up the prime number generation process as further explained below. The exponentiation unit is typically an arithmetic logic unit (ALU).
In accordance with conventional prime number generation methods, the generalized steps of randomly generating an odd number n0 and determining if the number n0 is a prime are executed sequentially using the arithmetic unit. If the number n0 is determined to be composite, a next prime number candidate n1 in a sequence of prime number candidates is generated by adding two to the previous number n0, and it is then determined if the number n1 is a prime. Furthermore, in accordance with conventional prime number generation methods, the t exponentiation tests in accordance with relationship (8) for α1, α2, . . . αt are typically executed in a sequential manner using the arithmetic unit to determine if each of the t tests declares “prime”.
Cryptographic key generation in accordance with conventional methods is very time consuming and processing intensive even with the use of fast arithmetic unit. Approximately 20 to 30 seconds is required to generate a cryptographic key value in a device such as a cell phone or PDA using conventional methods. This is partially due to the fact that the prime numbers in a predefined interval (e.g., the interval between 2L-1 and 2L) are far apart, and it is therefore necessary to perform tests on approximately L candidates that are determined to be composite before finding a prime number.
To summarize, the generation of cryptographic keys based on large prime numbers (such as for use in the classic two-prime RSA public key cryptosystem, and in the MultiPrime extension of the RSA system) is a computationally expensive problem requiring total operations on the order of the key length L (in bits) taken to the fourth power. As the need for stronger security forces the RSA public key cryptosystem cryptographic key lengths to grow from 512 to 1024, 2048, and 4096 bits, the time and cost of computer resources for generation of a new key grows correspondingly from 1 to 16 to 256 to 4096. In certain certificate authority applications, key management applications, secure server applications, and secure client applications, both the latency (elapsed time) and the throughput (transactions per second) of the end application involving key generation may be important to operational efficiency and economics or to user satisfaction. During periods of high demand, a queue of key generation requests may grow rapidly, causing a particular request to be delayed for many times the average key generation time, until all prior requests are completed. In addition, there are emerging secure applications where it would be beneficial to allow even more frequent changes of keys and issuance of new keys, if latency and queuing for new cryptographic keys was not so burdensome.
Previous approaches to solving the problems associated with latency and queuing for new cryptographic keys include: choice and optimization of algorithms for efficient large prime number searching via sieving and probablilistic primality testing of large integers; use of faster processors as available; and use of specialized processors and co-processors (including dedicated exponentiation units). All of these prior methods begin a key generation computation only after receipt of a request from an application.
What is needed is a system and method that provides large randomly generated prime numbers and cryptographic key parameters in response to requests therefor with a minimum amount of latency.
What is also needed is a system and method that provides a plurality of large randomly generated prime numbers and cryptographic key parameters where there is no statistical correlation or recurrence among the generated prime numbers so that the highest cryptographic security is maintained.